
#include <iostream>
#include <string>
using namespace std;

typedef struct ListNode {
	int val;
	struct ListNode *next;
} ListNode;

void scanList(ListNode* head){

	while(head) {
		cout << head->val;
		head = head->next;
	}
	cout<<endl;
}
//创建链表
ListNode* initLinked(int n[],int count){
	ListNode *head = new ListNode();
	ListNode *tmp =  new ListNode();
	for(int i=0; i<count; ++i){
		ListNode *node = new ListNode();
		node->val = n[i];
		tmp->next=node;
		tmp = node;
		if(i==0)
			head = tmp;
	}
	tmp->next = NULL;
	return head;
}

//合并
ListNode* merge(ListNode *first, ListNode* second) {

	if(first == NULL) {
		return second;
	}

	if (second == NULL) {
		return first;
	}
	if(first->val < second->val) {
		first->next = merge(first->next, second);
		return first;
	} else {
		second->next = merge(second->next, first);
		return second;
	}
}

//先递归拆分，再合并
ListNode* splitList(ListNode *node) {
	ListNode* slow = node;
	ListNode* fast = node;
	ListNode* breakPoint = node;
	if(node == NULL || node->next == NULL) {
		return node;
	}
	
	while(fast != NULL && fast->next != NULL) {
		fast = fast->next->next;
		breakPoint = slow;
		slow = slow->next;
	}
	breakPoint->next = NULL;
	ListNode* first = splitList(node);
	ListNode* second = splitList(slow);
	
	return merge(first, second);
}

int main() {
	ListNode* ptr = NULL;
	int n = 12;
	int a[n] = {3,4,5,1,2,3,-1,-2,-3,7,8,9};	
	ListNode* node = initLinked(a, n);
	ptr = splitList(node);
	scanList(ptr);
}